class Solution:
    _MOD = 1337

    def largestPalindrome(self, n: int) -> int:
        if n == 1:
            return 9

        hi = pow(10, n) - 1  # 最大的n位数
        lo = pow(10, n - 1)  # 最小的n位数

        for left in range(hi, lo - 1, -1):
            right = str(left)[::-1]
            num = int(str(left) + right)
            for factor in range(hi // 11 * 11, lo - 1, -11):  # 任意偶数长度的回文数均能被11整除
                a, b = divmod(num, factor)
                if b == 0 and lo <= a <= hi:
                    return num % self._MOD
                if a > hi:
                    break


if __name__ == "__main__":
    print(Solution().largestPalindrome(2))  # 987
